The present invention relates to an encoding apparatus and method, a decoding apparatus and method, and a providing medium, and particularly to an encoding apparatus and method, a decoding apparatus and method, and a providing medium which are suitably applied when encoding or decoding of a turbo code is performed.
A turbo code is known as a code showing performance close to Shannon limit as a theoretical limit of code performance. In this turbo code, encoding is performed through a structure in which a plurality of convolution encoding circuits and interleavers (interleave circuits) are combined, and at a decoding side, exchange of information concerning input data is made among a plurality of decoding circuits outputting soft outputs, so that a final decoding result is obtained.
FIG. 1 shows a structure of a conventional turbo encoding apparatus 10. This turbo encoding apparatus 10 includes a convolution encoding circuit 1-1 for performing convolution encoding with respect to input data to obtain encoded data, interleavers 2-1 to 2-(Nxe2x88x921) for sequentially interleaving the input data (hereinafter, in the case where it is not necessary to distinguish the interleavers 2-1 to 2-(Nxe2x88x921) individually, each is merely referred to as an interleaver 2. It is the same with other devices.), and convolution encoding circuits 1-2 to 1-N for performing convolution encoding with respect to the output data of the interleavers 2 respectively to obtain encoded data.
Here, the convolution encoding circuits 1 perform convolution encoding operations with respect to inputted data, and output the operation results respectively as encoded data. The interleavers 2 alter the sequence of inputted data and output them.
FIG. 2 shows an example of the convolution encoding circuit 1. The convolution encoding circuit shown in FIG. 2 is a feedback type convolution encoding circuit with a constraint length of three. This convolution encoding circuit 1 includes a termination circuit 21, three exclusive OR circuits (hereinafter referred to as xe2x80x9cEXOR circuitxe2x80x9d) 22-1 to 22-3, and two shift registers 23-1 and 23-2, and generates encoded data from input data.
Here, the shift register 23 functions as a delay element for delaying inputted data by one unit time, and the EXOR circuit 22 outputs exclusive OR of inputted data. The termination circuit 21 outputs the input data until all of the input data are encoded, and outputs feedback data for only a two-unit time (time corresponding to the number of the shift registers) from the point of time when encoding is completed. A process after all the input data are encoded is called a termination in which all the contents of the shift registers 23 are returned to zero, and the decoding side performs decoding on the assumption of this process.
FIG. 3 shows an example of the interleaver 2. The input data inputted to the interleaver 2 are temporarily stored in an input data holding memory 31, and then, sequence is rearranged by a data replacement circuit 32. The rearrangement of the sequence of the data is performed on the basis of the contents (replacement position information) of a replacement data ROM (Read Only Memory) 34. The data in which the sequence is rearranged are stored in an output data holding memory 33, and then, are outputted as output data.
FIG. 3 shows an example of an operation of the interleaver 2 in the case where the size of the interleaver 2 is five and the contents of the replacement data ROM 34 are as shown in FIG. 4. That is, when the input data are xe2x80x9c11010xe2x80x9d, in accordance with the data stored in the replacement data ROM 34, the data replacement circuit 32 performs a replacement process of the input data, so that xe2x80x9c00111xe2x80x9d are outputted as output data.
The operation of the turbo encoding apparatus 10 shown in FIG. 1 will be described. The input data are supplied to the convolution encoding circuit 1-1. In this convolution encoding circuit 1-1, a convolution encoding operation is performed to the input data, and the termination is subsequently performed, so that encoded data through the encoding process including the termination are outputted.
Besides, the input data are supplied to the series circuit of the interleavers 2-1 to 2-(Nxe2x88x921), and the sequence of the inputted data is sequentially altered and the data are outputted. The output data of the interleavers 2-1 to 2-(Nxe2x88x921) are supplied to the corresponding convolution encoding circuits 1-2 to 1-N, respectively. In the convolution encoding circuits 1-2 to 1-N, the convolution encoding operation is performed to the output data of the corresponding interleavers 2-1 to 2-(Nxe2x88x921) respectively, and the termination is subsequently performed, so that encoded data through the encoding process including the termination are outputted.
FIG. 5 shows the relation between the number of bits of input data and that of encoded data in the turbo encoding apparatus 10. After the inputted k-bit input data are converted into a n1-bit code by the convolution encoding circuit 1-1, a t1-bit termination code is further added, so that the data become a (n1+t1)-bit code in total. Similarly, (n2+t2) to (nm+tm)-bit encoded data are outputted from the convolution encoding circuits 1-2 to 1-N.
FIG. 6 shows a structure of a conventional turbo decoding apparatus 40. This turbo decoding apparatus 40 includes a plurality of soft output decoding circuits 51-1 to 51-N corresponding to the number of encoded data (reception data) outputted from the turbo encoding apparatus 10. The soft output decoding circuits 51-1 to 51-N are structured by using a so-called soft output decoding system having a function to calculate a probability that the input data at the encoding side is 0 or 1, such as a MAP (Maximum Aposteriori Probability) decoder and a SOVA (Soft Output Viterbi Algorithm) decoder.
The operation of the turbo decoding apparatus 40 shown in FIG. 6 will be described. The reception data (encoded data) are supplied to the soft output decoding circuits 51-1 to 51-N, respectively. The respective decoding circuits 51-1 to 51-N mutually use estimation probability value data with respect to the input data except the termination bit at the encoding side, and several to several tens repetitive decoding operations are performed. Final decoded data are outputted from an arbitrary decoding circuit (in FIG. 6, the decoding circuit 51-1).
FIG. 7 shows the relation among the number of bits of the reception data of the turbo decoding apparatus 40, that of the estimation probability value data, and that of the decoded data, and corresponds to the relation of the respective numbers of bits in the turbo encoding apparatus 10 in FIG. 1. The soft output decoding circuits 51-1 to 51-N calculate k-bit estimation probability value data of the input data except the termination bit from the (n1+t1) to (nm+tm)-bit reception data. The k-bit estimation probability value data are exchanged among the respective decoding circuits, and k-bit decoded data are finally outputted.
Now, for the purpose of obtaining a high error correction capability in a turbo encoding apparatus and a decoding apparatus, in general, it is necessary that the interleaver 2 satisfies the following two conditions at the same time.
[Condition 1] The sum of distances between arbitrary two points after-replacement becomes sufficiently larger than that before the replacement.
[Condition 2] In the case where replacement positions are regarded as a sequence, the sequence satisfies a mathematical property called k-equidistributioness.
The foregoing two conditions relate to performance index values defined for an error correction code, which are called a minimum distance of a code and a multiplicity of a minimum distance code. These two conditions are necessitated in order for the error correction code to show excellent performance. The condition 1 corresponds to that the minimum distance becomes large, and the condition 2 corresponds to that the multiplicity of the minimum distance code becomes small.
However, in the interleaver 2 of the foregoing turbo encoding apparatus 10, data stored in the replacement data ROM 34 and generated by using random numbers are used as data for determining replacement positions. In the replacement positions generated as a result of use of such random numbers, the k-equidistributioness of the condition 2 can be satisfied. However, since there occurs a case where the sum of distances between arbitrary two points before and after the replacement becomes small, the condition 1 can not be satisfied.
Other than the interleaver to determine a replacement position by using random numbers, there is an affine interleaver. Although this affine interleaver is suitable as an interleaver satisfying the condition 1, it can not satisfy the condition 2.
Like this, in the conventionally used interleaver, there has been a problem that the foregoing condition 1 and the condition 2 can not be satisfied at the same time.
The present invention has been made in view of such circumstances, and an object of the invention is to provide an interleaver satisfying the foregoing condition 1 and the condition 2 at the same time.
An encoding apparatus, an encoding method, and a providing medium of the invention are characterized in that interleave means replaces the input data by using an interleaver in which the sum of distances between arbitrary two points before and after replacement is a predetermined value or more, and further randomizes the replaced input data.
A decoding apparatus, a decoding method, and a providing medium are characterized by performing a deinterleave process opposite to an interleave process performed by the encoding apparatus.